package net.cyndeline.rlgraph.embedding.immutable

import scala.collection.mutable
import net.cyndeline.rlgraph.embedding.{AdjacencyList, AdjacencyEntry, PlanarEmbedding}
import net.cyndeline.rlgraph.embedding.mutable.{DoublyLinkedList, DoublyLinkedEntry}
import scala.collection.mutable.ArrayBuffer
import scalax.collection.GraphEdge.UnDiEdge
import scalax.collection.immutable.Graph
import scalax.collection.GraphPredef._

/**
 * Stores the circular order of edges around each vertex in a graph.
 *
 * @tparam VType Type of nodes used in the graph being embedded.
 */
class UndirectedEmbedding[VType : Manifest] extends PlanarEmbedding[VType] {
  private val embeddings = mutable.HashMap[VType, DoublyLinkedList[VType]]()
  private var empty = true

  private def this(map: mutable.HashMap[VType, DoublyLinkedEntry[VType]]) {
    this()
    val values = map.iterator
    while (values.hasNext) {
      val vertexAndEntry = values.next()
      val vertex = vertexAndEntry._1
      val headEntry = vertexAndEntry._2
      embeddings.put(vertex, new DoublyLinkedList(vertex, headEntry))
    }

    empty = embeddings.isEmpty
  }

  /**
   * Checks if the embedding contains any vertices (a prerequisite for containing edges,
   * and vice versa).
   * @return True if the embedding has at least one edge embedded, otherwise false.
   */
  override def isEmpty: Boolean = empty

  /**
   * Retrieves the head element in the list of edges connected to a single vertex in a graph. Note that this
   * element is arbitrarily chosen as Head, as the list is circular.
   *
   * @param vertex The vertex to retrieve an embedding for.
   * @return the head of an adjacency list for the specified vertex, or none if the vertex isn't present in the
   *         embedding.
   */
  override def embeddingFor(vertex: VType): Option[AdjacencyList[VType]] = embeddings.get(vertex)

  /**
   * @return every vertex in the embedding.
   */
  override def embeddedVertices: List[VType] = embeddings.keys.toList

  /**
   * @return every vertex and its head entry in the embedding.
   */
  override def iterator: Iterator[(VType, AdjacencyList[VType])] = embeddings.iterator

  /**
   * Embeds a new edge.
   * @param head A vertex to be embedded.
   * @param tail A vertex to be embedded, belonging to the same edge as the Head.
   * @return A new embedding with the edge added to it, or the same embedding if both vertices already exist and
   *         contain an edge between each other.
   */
  override def embed(head: VType, tail: VType): PlanarEmbedding[VType] = embed(head, tail, None, None)

  /**
   * Embeds a new edge. Regardless of weather the edge is undirected or directed,
   * it contains a head and a tail node (these are arbitrary on undirected edges).
   * Vertices will be given an empty adjacency list if they're not already present,
   * and each will have the opposite node added to its embedding.
   *
   * Example usage: embed(A, B, A_C, B_F)
   *
   * The above call embeds an edge between A and B. Both A and B exists in the embeddings, but does not have
   * an edge inserted between them. The entry of B will be inserted in A's adjacency list after the edge entry
   * pointing to the vertex C. The entry of A in B will be inserted after the entry pointing to the vertex F.
   *
   * Example usage: embed(A, B, A_C, None)
   *
   * This call can be made to embed the edge (A, B) if B doesn't already exist in the embedding (the entry to A will be
   * the only entry in B's adjacency list, and thus does not need a specified position), or if the entry of A in B may
   * be inserted at an arbitrary position.
   *
   * @param head A vertex to be embedded.
   * @param tail A vertex to be embedded, belonging to the same edge as the Head.
   * @param headPos Node that the Head should be placed after in the Tails embedding. None if it should be
   *                added to the end of the adjacency list or if this is the first edge to embedded into the tail.
   * @param tailPos Node that the Tail should be placed after in the Heads embedding. None if it should be
   *                added to the end of the adjacency list or if this is the first edge to embedded into the head.
   * @return A new embedding with the edge added to it.
   */
  override def embed(head: VType, tail: VType, headPos: Option[VType], tailPos: Option[VType]): PlanarEmbedding[VType] = {
    if (embeddingExists(head, tail)) return this
    if (head == tail) throw new IllegalArgumentException("Attempted to embed an edge beginning and ending in the same vertex (" + head + ")")

    if (headPos.isDefined && (embeddingFor(tail).isEmpty || !embeddingFor(tail).get.containsEntryFor(headPos.get)))
      throw new IllegalArgumentException("Attempted to specify insert position for " + head + " as " + headPos.get + " in the vertex " + tail + ", but that position doesn't exist.")

    if (tailPos.isDefined && (embeddingFor(head).isEmpty || !embeddingFor(head).get.containsEntryFor(tailPos.get)))
      throw new IllegalArgumentException("Attempted to specify insert position for " + tail + " as " + tailPos.get + " in the vertex " + head + ", but that position doesn't exist.")

    var verticesAndEmbeddings: Iterator[(VType, DoublyLinkedEntry[VType])] = verticesAndHeadEntries(embeddings)
    val newEmbedding = mutable.HashMap[VType, DoublyLinkedEntry[VType]]()
    val tempEmbedding = mutable.HashMap[VType, List[DoublyLinkedEntry[VType]]]()

    /*
     * STEP 1: Copy all previous embeddings to the new one.
     */
    while (verticesAndEmbeddings.hasNext) {
      val pair: (VType, DoublyLinkedEntry[VType]) = verticesAndEmbeddings.next
      val vertex = pair._1

      val copiedAdjacencyEntries = for (entry <- entryList(pair._2)) yield new DoublyLinkedEntry(entry.vertex)

      /* Store them temporarily */
      tempEmbedding.put(vertex, copiedAdjacencyEntries)

      /* Link next and previous */
      var tmp: DoublyLinkedEntry[VType] = null
      var head: DoublyLinkedEntry[VType] = null
      for (entry <- copiedAdjacencyEntries) {
        if (tmp != null) {
          entry.previousEntry = tmp
          tmp.nextEntry = entry
        }

        if (head == null) head = entry
        tmp = entry
      }

      /* If the embedding contains only one edge, both head and tmp will be it. */
      if (tmp != null) {
        tmp.nextEntry = head
        head.previousEntry = tmp

        newEmbedding.put(vertex, head)
      }
    }

    /* For every edge, see if its movement entry in the other vertex in the edge has been embedded.
     * If not, add movement links to both. Since double links are used here as well, this cannot be
     * done until every adjacency entry has been added to the new embedding.
     */
    verticesAndEmbeddings = verticesAndHeadEntries(embeddings)
    while (verticesAndEmbeddings.hasNext) {
      val vertexAndAdjacencyList: (VType, AdjacencyEntry[VType]) = verticesAndEmbeddings.next
      val vertexA = vertexAndAdjacencyList._1
      val embeddedEdges: List[DoublyLinkedEntry[VType]] = tempEmbedding(vertexA)

      val entriesForB = embeddedEdges.iterator
      while (entriesForB.hasNext) {
        val entryForB = entriesForB.next

        /* Since two entries movement links are updated simultaneously, checking that one of them is null
         * is enough to see if both need linking.
         */
        if (entryForB.moveTo == null) {
          val vertexB = entryForB.vertex
          val entryForAinB = findVertexEntry(vertexB, vertexA, tempEmbedding)
          entryForB.move = entryForAinB
          entryForAinB.move = entryForB
        }
      }
    }

    /*
     * STEP 2: Add the new edge.
     */
    val headEntry = new DoublyLinkedEntry(head)
    val tailEntry = new DoublyLinkedEntry(tail)
    headEntry.move = tailEntry
    tailEntry.move = headEntry

    addVertexEntry(tail, headEntry, headPos, newEmbedding)
    addVertexEntry(head, tailEntry, tailPos, newEmbedding)

    new UndirectedEmbedding(newEmbedding)
  }

  /**
   * Creates a new embedding by joining two embeddings together in a single vertex, at a position
   * in this embedding specified by the user.
   *
   * @param other Embedding to combine with this one.
   * @param positions Edges in this embedding, mapped towards the vertex of the entry that any edges from 'other
   *                  should be inserted after. This map needs to have a key for every vertex common to both embeddings,
   *                  or an IllegalArgumentException will be thrown.
   * @return A new embedding with all edges from both previous embeddings. The shares vertex will contain edges
   *         from both embeddings, and all edges from a single embedding will retain the circular order they had
   *         before the join.
   */
  override def join(other: PlanarEmbedding[VType], positions: Map[VType, VType]): PlanarEmbedding[VType] = {
    val commonVertices = (embeddings.keySet intersect other.embeddedVertices.toSet).toSet

    /* Every connecting vertex must be specified in the position map. */
    if (commonVertices != positions.keySet) {
      throw new IllegalArgumentException("The positions " + positions + " does not equal the set of common vertices in both embeddings: " + commonVertices)
    }

    val allEmbeddings = new mutable.HashMap[VType, DoublyLinkedEntry[VType]]()

    /* Copy every vertex entry list of this embedding, and every vertex save for the mutual ones in
     * the other embedding.
     */
    copyEmbeddingToMap(this, allEmbeddings, Set())
    copyEmbeddingToMap(other, allEmbeddings, commonVertices)

    val commons = commonVertices.iterator
    while (commons.hasNext) {
      val vertex = commons.next // The vertex in the embedding that will have its entry list augmented
      val entry = other.embeddingFor(vertex).get // The current head of the embedded entries in 'other
      val insertionPosition = positions.get(vertex).get // Where in the final embedding to insert the list from 'other
      val insertionListCopy: DoublyLinkedEntry[VType] = copyEntryList(entry.head) // A new copy of the entries to insert

      val currentList: DoublyLinkedEntry[VType] = allEmbeddings.get(vertex).get
      insertEntryIntoList(insertionListCopy, insertionPosition, currentList)
    }

    /* Set up movement links between all entries in the final embedding. */
    val embeddedEntries = allEmbeddings.iterator
    val embeddingConvertedToHeadEntries = convertEntryMapToList(allEmbeddings)
    while (embeddedEntries.hasNext) {
      val entry: (VType, DoublyLinkedEntry[VType]) = embeddedEntries.next
      val vertex = entry._1
      val listHead = entry._2

      for (listEntry <- entryList(listHead)) {
        if (listEntry.move == null) {
          val correspondingEntry = findVertexEntry(listEntry.vertex, vertex, embeddingConvertedToHeadEntries)
          listEntry.move = correspondingEntry
          correspondingEntry.move = listEntry
        }
      }
    }

    new UndirectedEmbedding[VType](allEmbeddings)
  }

  /**
   * Converts the embedding into an undirected graph.
   *
   * @return A graph containing all vertices in the embedding, with edges constructed by the factory according to
   *         the embedded edge entries.
   */
  override def toUndirectedGraph(): Graph[VType, UnDiEdge] = {
    val edges = new ArrayBuffer[UnDiEdge[VType]]()
    val vertices = this.embeddedVertices.iterator

    while (vertices.hasNext) {
      val vertex = vertices.next()
      val adjacencyEntries: Iterator[AdjacencyEntry[VType]] = this.embeddingFor(vertex).get.iterator

      while (adjacencyEntries.hasNext) {
        val entry = adjacencyEntries.next()
        edges += vertex~entry.vertex
      }
    }

    Graph.from(embeddedVertices, edges.toList)
  }

  override def toString: String = {
    val buffer = new StringBuilder()
    val it = embeddings.iterator

    buffer ++= "Undirected embedding\n"

    while (it.hasNext) {
      val entry: (VType, DoublyLinkedList[VType]) = it.next()
      buffer ++= entry._1.toString + " -> " + entry._2.toString() + "\n"
    }

    buffer.mkString
  }

  /**
   * Updates an entry list by inserting another list of entries after a particular entry.
   * @param head Head element in the list to insert.
   * @param position Vertex entry to insert the head element after.
   * @param list Head of the list that will have elements inserted in it.
   */
  private def insertEntryIntoList(head: DoublyLinkedEntry[VType], position: VType, list: DoublyLinkedEntry[VType]) {
    val tail = head.previousEntry
    val insertionPosition = findEntry(list, list, position)
    val insertionNext = insertionPosition.nextEntry

    insertionPosition.nextEntry = head
    head.previousEntry = insertionPosition
    insertionNext.previousEntry = tail
    tail.nextEntry = insertionNext
  }

  /**
   * Uses interfaces to handles external embeddings.
   */
  private def copyEmbeddingToMap(embedding: PlanarEmbedding[VType], copyTo: mutable.HashMap[VType, DoublyLinkedEntry[VType]], skip: Set[VType]) {
    val entries: Iterator[(VType, AdjacencyList[VType])] = embedding.iterator

    while (entries.hasNext) {
      val entry = entries.next()
      val vertex = entry._1
      if (!skip.contains(vertex)) {
        val copiedEntryList = copyEntryList(entry._2.head)
        copyTo += (entry._1 -> copiedEntryList)
      }

    }
  }

  /**
   * Creates a copy of an adjacency list with next/previous set, but leaves the move values as null.
   */
  private def copyEntryList(h: AdjacencyEntry[VType]): DoublyLinkedEntry[VType] = {
    var previous: DoublyLinkedEntry[VType] = null
    var head: DoublyLinkedEntry[VType] = null

    for(entry <- entryListInterf(h)) {
      val copy = new DoublyLinkedEntry[VType](entry.vertex)

      if (head == null) head = copy

      if (previous != null) {
        previous.nextEntry = copy
        copy.previousEntry = previous
      }

      previous = copy
    }

    head.previousEntry = previous
    previous.nextEntry = head
    head
  }

  private def entryList(entry: DoublyLinkedEntry[VType], result: List[DoublyLinkedEntry[VType]] = Nil): List[DoublyLinkedEntry[VType]] = {
    if (result.isEmpty || (!result.isEmpty && result.head != entry)) {
      entryList(entry.nextEntry, result :+ entry)
    } else {
      result
    }
  }

  private def entryListInterf(entry: AdjacencyEntry[VType], result: List[AdjacencyEntry[VType]] = Nil): List[AdjacencyEntry[VType]] = {
    if (result.isEmpty || (!result.isEmpty && result.head != entry)) {
      entryListInterf(entry.next, result :+ entry)
    } else {
      result
    }
  }

  private def embeddingExists(a: VType, b: VType): Boolean = {
    if (embeddings.contains(a) && embeddings.contains(b)) {
      val aEntries = embeddings(a)
      val bEntries = embeddings(b)

      aEntries.containsEntryFor(b) && bEntries.containsEntryFor(a)
    } else {
      false
    }
  }

  private def addVertexEntry(v: VType, entry: DoublyLinkedEntry[VType], position: Option[VType], listMapping: mutable.HashMap[VType, DoublyLinkedEntry[VType]]) {
    if (!listMapping.contains(v)) {
      entry.nextEntry = entry
      entry.previousEntry = entry
      listMapping.put(v, entry)

    } else if(position.isEmpty) {
      val head = listMapping(v)
      val lastEntry = head.previousEntry
      lastEntry.nextEntry = entry
      entry.previousEntry = lastEntry
      entry.nextEntry = head
      head.previousEntry = entry

    } else {
      val startEntry = listMapping(v)
      val positionEntry = findEntry(startEntry, startEntry, position.get)

      if (positionEntry == null) throw new IllegalArgumentException("Attempted to add entry " + entry.vertex + " to vertex " + v + ", but the position " + position.get + " could not be found.")

      val next = positionEntry.nextEntry
      entry.previousEntry = positionEntry
      entry.nextEntry = next
      next.previousEntry = entry
      positionEntry.nextEntry = entry
    }
  }

  private def findVertexEntry(vertexToSearch: VType, vertexEntryToSearchFor: VType, listMapping: mutable.HashMap[VType, List[DoublyLinkedEntry[VType]]]): DoublyLinkedEntry[VType] = {
    for (entryListHead: DoublyLinkedEntry[VType] <- listMapping(vertexToSearch)) {
      for (entry: DoublyLinkedEntry[VType] <- entryList(entryListHead)) {
        if (entry.vertex == vertexEntryToSearchFor) return entry
      }
    }

    null  // Shouldn't happen
  }

  private def convertEntryMapToList(listMapping: mutable.HashMap[VType, DoublyLinkedEntry[VType]]): mutable.HashMap[VType, List[DoublyLinkedEntry[VType]]] = {
    val listToEntry: mutable.HashMap[VType, List[DoublyLinkedEntry[VType]]] = for ((key, value) <- listMapping) yield (key, entryList(value))
    listToEntry
  }

  private def findEntry(start: DoublyLinkedEntry[VType], current: DoublyLinkedEntry[VType], vertexToFind: VType): DoublyLinkedEntry[VType] = current match {
    case entry: DoublyLinkedEntry[VType] => if (entry.vertex == vertexToFind) {
      entry
    } else if (current.next.vertex != start.vertex) {
      findEntry(start, current.nextEntry, vertexToFind)
    } else {
      null // Shouldn't happen
    }

    case _ => null
  }

  private def verticesAndHeadEntries(embedding: mutable.HashMap[VType, DoublyLinkedList[VType]]): Iterator[(VType, DoublyLinkedEntry[VType])] = {
    val result = ArrayBuffer[(VType, DoublyLinkedEntry[VType])]()
    val currentMapping: Iterator[(VType, DoublyLinkedList[VType])] = embedding.iterator
    while(currentMapping.hasNext) {
      val e = currentMapping.next()
      result += ((e._1, e._2.head))
    }

    result.iterator
  }
}
